# -*- coding: utf-8 -*-

"""712. 两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:
输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:
输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

提示:
0 <= s1.length, s2.length <= 1000
s1 和 s2 由小写英文字母组成"""

class Solution:
    """
         d    e    l    e    t    e
    l    0    0    108  0    0    0
    e    0    101  0    101  0    101
    e    0    101  0    101  0    101
    t    0    0    0    0    116  0
    这个问题经过转化就成为，从首行到尾行，如果经过大于0的点，可以往右下方走一步，如果经过等于0的点，可以往右或者往下走一步。
    到达尾行所经过点的最大值。
    定义 f(i,j) 为到达位置 (i,j) 处的路径上的最大和。不过这道题本身就更适合用递推直接做。
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+commom[i][j])    # 当 dp[i][j] > 0
        dp[i][j+1] = max(dp[i][j+1], dp[i][j]+common[i][j+1])      # 当 dp[i][j] = 0
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]+commom[i+1][j])      # 当 dp[i][j] = 0

    递推基础：
        dp[0][j] = common[0][j]
    """
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        totalSum = sum([ord(c1) for c1 in s1]) + sum([ord(c2) for c2 in s2])
        if s1 == '' or s2 == '':
            return totalSum

        s1, s2 = s1+'1', s2+'2'
        d1, d2 = len(s1), len(s2)
        common = [ [0 for _ in range(d1)] for _ in range(d2)]
        i = 0
        while i < d2:
            j = 0
            while j < d1:
                if s2[i] == s1[j]:
                    common[i][j] = ord(s2[i])
                j += 1
            i += 1

        # for foo in common:
        #     print(foo)

        dp = [ [0 for _ in range(d1)] for _ in range(d2)]
        j = 0
        while j < d1:
            dp[0][j] = common[0][j]
            j += 1

        maxSum = 0

        i = 0
        while i < d2-1:
            j = 0
            while j < d1-1:
                maxSum = max(maxSum, dp[i][j])
                if common[i][j]:
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+common[i+1][j+1])
                else:
                    dp[i][j+1] = max(dp[i][j+1], dp[i][j]+common[i][j+1])
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j]+common[i+1][j])
                j += 1
            i += 1
        # print('------')
        # for bar in dp:
        #     print(bar)

        return totalSum-2*maxSum

if __name__ == '__main__':
    rs = Solution().minimumDeleteSum(s1 = "delete", s2 = "leet")
    print(rs)
